package offer2

/*
原题链接:
https://leetcode.cn/problems/zhong-jian-er-cha-shu-lcof/?favorite=xb9nqhhg

B站 小美算法讲解
剑指 Offer 07. 重建二叉树
输入某二叉树的前序遍历和中序遍历的结果，请构建该二叉树并返回其根节点。
假设输入的前序遍历和中序遍历的结果中都不含重复的数字。

示例 1:
Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
Output: [3,9,20,null,null,15,7]

示例 2:
Input: preorder = [-1], inorder = [-1]
Output: [-1]
*/

type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

func buildTree(preorder []int, inorder []int) *TreeNode {
	//1.如果前序遍历数组长度为0,返回nil
	if len(preorder) == 0 {
		return nil
	}

	//2.以前序遍历 0索引元素作为根节点
	node := &TreeNode{preorder[0], nil, nil}

	//3.找到 inorder中序遍历数组中 根元素所在的下标
	index := 0
	for ; index < len(inorder); index++ {
		if preorder[0] == inorder[index] {
			break
		}
	}

	//4.分别将前序遍历、中序遍历数组，拆分为左右节点的前序、中序遍历数组
	leftPre := preorder[1 : index+1]
	rightPre := preorder[index+1:]

	leftIn := inorder[:index]
	rightIn := inorder[index+1:]

	//5.递归构建左右子节点
	node.Left = buildTree(leftPre, leftIn)
	node.Right = buildTree(rightPre, rightIn)

	return node
}
